package com.ma.graph;

import java.util.*;

class State {
    int id;
    int distFromStart;

    public State(int id, int distFromStart) {
        this.id = id;
        this.distFromStart = distFromStart;
    }
}


public class Solution743 {

    //Dijkstra 算法
    public static int[] dijkstra(int start, List<int[]>[] graph) {
        //初始化distTo数组
        int[] distTo = new int[graph.length];
        Arrays.fill(distTo, Integer.MAX_VALUE);
        distTo[start] = 0;

        Queue<State> pq = new PriorityQueue<>((a, b) -> {
            return a.distFromStart - b.distFromStart;
        });
        pq.offer(new State(start, 0));

        while (!pq.isEmpty()) {
            State curNode = pq.poll();
            int curNodeId = curNode.id;
            int curDistFromStart = curNode.distFromStart;
            if (curDistFromStart > distTo[curNodeId]) {
                continue;
            }
            for (int[] neighbor : graph[curNodeId]) {
                int nextNodeId = neighbor[0];
                int distToNextNode = distTo[curNodeId] + neighbor[1];
                if (distToNextNode < distTo[nextNodeId]) {
                    distTo[nextNodeId] = distToNextNode;
                    pq.offer(new State(nextNodeId, distTo[nextNodeId]));
                }
            }
        }
        return distTo;
    }

    public static int networkDelayTime(int[][] times, int n, int k) {
        /*利用Dijkstra算法，计算n节点到所有节点的最短路径
          最短路径最长的即为结果，如果有到达不了的点，返回-1
        */
        //索引从1开始  废弃索引0  需要n+1长度
        List<int[]>[] graph = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        //构造带权值信息的邻接图
        for (int[] edge : times) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            graph[from].add(new int[]{to, weight});
        }
        //调用Dijkstra算法，得到k到其他节点的最短路径
        int[] distTo = dijkstra(k, graph);
        int res = 0;
        for (int i = 1; i < distTo.length; i++) {
            //存在不可达节点，返回-1
            if (distTo[i] == Integer.MAX_VALUE) {
                return -1;
            }
            //得到最远可达节点的路径即为所需结果
            res = Math.max(res, distTo[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        int n = 4;
        int k = 2;
        int i = networkDelayTime(times, n, k);
        System.out.println(i);


    }

}
